ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน a และ b ค่าตัวหารร่วมมาก g เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง a และ b ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ ตัวประกอบร่วมค่ามากสุด (อังกฤษ: greatest common factor,GCF), ตัวประกอบร่วมค่ามากสุด(อังกฤษ: highest common factor,HCF) และ greatest common measure (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย หรม.(a, b) หรือ (a, b),[3] แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ

ถ้า หรม.(a, b) = 1 แล้ว a กับ b เป็นจำนวนเฉพาะสัมพัทธ์[4] ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า a หรือ b เป็นจำนวนเฉพาะเองแต่อย่างใด[5] เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 7 อย่างไรก็ตาม 6 และ 35 เป็นจำนวนเฉพาะสัมพัทธ์ ไม่มีจำนวนธรรมชาตินอกเหนือจาก 1 หารทั้ง 6 และ 35 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน